package Leetcode.Stack;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @Author: kirito
 * @Date: 2024/4/16 12:44
 * @Description:
 * 132 模式
 * 已解答
 * 中等
 * 相关标签
 * 相关企业
 * 给你一个整数数组 nums ，数组中共有 n 个整数。132 模式的子序列 由三个整数 nums[i]、nums[j] 和 nums[k] 组成，并同时满足：i < j < k 和 nums[i] < nums[k] < nums[j] 。
 *
 * 如果 nums 中存在 132 模式的子序列 ，返回 true ；否则，返回 false 。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [1,2,3,4]
 * 输出：false
 * 解释：序列中不存在 132 模式的子序列。
 * 示例 2：
 *
 * 输入：nums = [3,1,4,2]
 * 输出：true
 * 解释：序列中有 1 个 132 模式的子序列： [1, 4, 2] 。
 * 示例 3：
 *
 * 输入：nums = [-1,3,2,0]
 * 输出：true
 * 解释：序列中有 3 个 132 模式的的子序列：[-1, 3, 2]、[-1, 3, 0] 和 [-1, 2, 0] 。
 *
 *
 * 提示：
 *
 * n == nums.length
 * 1 <= n <= 2 * 105
 * -109 <= nums[i] <= 109
 *
 */

public class find132pattern {
    public static void main(String[] args) {
        int[] nums = {3,1,4,2,1};
        System.out.println(find132pattern(nums));
    }
    public static boolean find132pattern(int[] nums) {
        // 获取数组的长度
        int n = nums.length;
        // 使用LinkedList实现的Deque来存储可能的K值
        Deque<Integer> candidateK = new LinkedList<Integer>();
        // 初始化candidateK的栈顶元素为数组的最后一个元素
        candidateK.push(nums[n - 1]);
        // 初始化最大K值
        int maxK = Integer.MIN_VALUE;

        // 从数组的倒数第二个元素开始向前遍历
        for (int i = n - 2; i >= 0; --i) {
            // 如果当前元素小于栈顶元素（即可能的K值），说明找到了132模式
            if (nums[i] < maxK) {
                return true;
            }
            // 如果当前元素大于栈顶元素，则弹出栈顶元素，更新最大K值
            //k应该取比j小，但是是j右边最大得数
            while (!candidateK.isEmpty()
                    && nums[i] > candidateK.peek()) {
                maxK = candidateK.pop();
            }
            // 如果当前元素大于当前的最大K值，则将当前元素压入栈顶
            if (nums[i] > maxK) {
                candidateK.push(nums[i]);
            }
        }

        // 如果没有找到132模式，返回false
        return false;
    }

    //有一点问题还没完善
    //maxK不能取最小，这样的话满足要求得可能i属于j-k,但k是最小的，会导致i没办法取到合适得值
//    public static boolean find132pattern2(int[] nums) {
//        int len = nums.length;
//        int[] maxK = new int[len];
//        maxK[len - 1] = nums[len - 1];
//        //从左往右记录当前索引右边最小得数
//        for (int i = len - 2; i >=0; i--) {
//            if (maxK[i + 1] < nums[i]) {
//                maxK[i] = nums[i + 1];
//            }else{
//                maxK[i] = maxK[i+1];
//            }
//        }
//        int min_first = nums[0];
//        for (int i = 1; i < len - 2; i++) {
//            if (nums[i] > min_first) {
//                if(nums[i] > maxK[i+1] && maxK[i+1] > min_first){
//                    return true;
//                }
//            }else{
//                min_first = nums[i];
//            }
//        }
//
//        return false;
//    }
}
